class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        sorted_array = Solution.quick_sort_default(numbers)
        mid_index = len(sorted_array)//2
        mid = sorted_array[mid_index]
        mid_count = 0
        for i in range(len(sorted_array)):
            if sorted_array[i] == mid:
                mid_count+=1
        if mid_count >  (len(sorted_array))//2:
            return mid
        else:
            return 0

    @staticmethod
    def quick_sort_default(array):
        Solution.quick_sort(array, 0, len(array)-1)
        return array

    @staticmethod
    def quick_sort(array, lo, hi):
        if hi - 2 < lo:
            return
        m = Solution.partition(array, lo, hi)
        Solution.quick_sort(array, lo, m)
        Solution.quick_sort(array, m+1, hi)

    @staticmethod
    def partition(array, lo, hi):
        import random
        backup = array[lo]
        pivot_index = random.randint(lo, hi)
        pivot = array[pivot_index]
        Solution.swap(array, pivot_index, lo)
        while lo < hi:
            while lo < hi and array[hi] >= pivot:
                hi -= 1
            array[lo] = array[hi]
            while lo < hi and array[lo] <= pivot:
                lo += 1
            array[hi] = array[lo]
        array[lo] = pivot
        return lo

    @staticmethod
    def swap(array, index1, index2):
        temp = array[index1]
        array[index1] = array[index2]
        array[index2] = temp
        
